#include<iostream>
#include<vector>
using namespace std;

vector<int> x; // 解向量, 全局变量

// 输出一个解
void disp(vector<int> &a)
{
	printf("   {");
	for (int i=0; i<x.size(); i++)
		if (x[i]==1)
			printf("%d", a[i]);
	printf("}");
}

// 递归回溯算法
void dfs(vector<int> &a, int i)
{
	if (i >= a.size())
		disp(a);
	else
	{
		x[i] = 1;
		dfs(a, i+1);	 // 选择a[i]
		x[i] = 0;
		dfs(a, i+1);	 // 不选择a[i]
	}
}

// 求a的幂集
void subsets(vector<int>&a)
{
	// 求a的长度
	int n = a.size();
	
	// 指定x的长度为n
	x.resize(n);
	
	// 回溯求子集
	dfs(a, 0);
}

int main()
{
	// 初始化向量
	vector<int> a{1, 2, 3};
	
	// 解向量，初始化为0 
	vector<int> x(a.size(), 0);
	
	// 求所有子集
	printf("求解结果\n");
	subsets(a);
	printf("\n");
	return 0; 
}
